#include <cstdio>
#include <queue>
#include <cstring>
#include <vector>
using namespace std;

int n, e, m, f[ 100001 ], in[ 100001 ], father[ 100001 ], out[ 100001 ];
bool visit[ 100001 ];
vector<int> li[ 100001 ];

struct cmp
{
    bool operator ()( int a, int b )
    {
        return f[ a ] < f[ b ];
    }
};

void bfs( int p )
{
    queue<int> q;
    int i;
    q.push( p );
    while ( !q.empty( ) )
    {
        p = q.front( ); q.pop( );
        for ( i = 0; i < li[ p ].size( ); i++ )
        {
            f[ li[ p ][ i ] ] = f[ p ] + 1;
            q.push( li[ p ][ i ] );
        }
    }
}

void init( )
{
    int i, u, v;
    memset( f, 0, sizeof( f ) );
    memset( visit, 0, sizeof( visit ) );
    memset( in, 0, sizeof( in ) );
    memset( out, 0, sizeof( out ) );
    scanf("%d%d%d", &n, &e, &m);
    for ( i = 0; i < n; i++ )
    {
        li[ i ].clear( );
        father[ i ] = -1;
    }
    for ( i = 0; i < e; i++ )
    {
        scanf("%d%d", &u, &v); u--; v--;
        in[ u ]++;
        father[ u ] = v;
        out[ v ]++;
        li[ v ].push_back( u );
    }
    for ( i = 0; i < n; i++ )
        if ( !in[ i ] )
            bfs( i );
}

void work( )
{
    int i, p, ans = 0;
    priority_queue<int, vector<int>, cmp> q;
    queue<int> qq;
    for ( i = 0; i < n; i++ )
        if ( !out[ i ] )
            q.push( i );
    while ( !q.empty( ) )
    {
        ans++;
        for ( i = 0; i < m && !q.empty( ); i++ )
        {
            p = q.top( ); q.pop( );
            out[ father[ p ] ]--;
            if ( !out[ father[ p ] ] )
                qq.push( father[ p ] );
        }
        while ( !qq.empty( ) )
        {
            q.push( qq.front( ) );
            qq.pop( );
        }
    }
    printf("%d\n", ans);
}

int main( )
{
    int t;
    scanf("%d", &t);
    while ( t-- )
    {
        init( );
        work( );
    }
    return 0;
}
